#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;
#define infinity (1e9)
#define kSize 3  /* 棋盘规模为 kSize x kSize */
#define kMaxStates 362880 /* 共有 9! 种状态 */
typedef struct StateNode *States;
struct StateNode {
    long long s; /* 用64位长整型存储棋盘 */
    int g; /* 从初始状态到此状态的步数 */
    int f; /* 从初始状态到此状态再到目标状态的步数 */
    States parent; /* 记录到达此状态的前一个状态 */
};

/* 关于OPEN和CLOSED表的定义与操作 */
typedef struct TableNode *Tables;
struct TableNode {
    States t[kMaxStates];
    int size;
};

bool IsEmpty(Tables table) {
    /* 判断表是否为空 */
    return (table->size == 0);
}

bool IsIn(Tables table, States state) {
    /* 判断state是否在表中 */
    int i;

    for (i = 0; i < table->size; i++) {
        if (table->t[i]->s == state->s) {
            break;
        }
    }
    return (i < table->size);
}

void Insert(Tables table, States state) {
    /* 将state插入表中 */
    table->t[table->size] = state;
    table->size++;
}

void Remove(Tables table, States state) {
    /* 将state从表中删除 */
    int i;

    for (i = 0; i < table->size; i++) {
        if (table->t[i]->s == state->s) {
            break;
        }
    }
    if (i == table->size) {
        printf("错误：待删除元素不存在。\n");
    } else {
        table->t[i] = table->t[table->size - 1];
        table->size--;
    }
}

States ExtractMin(Tables table) {
    /* 简单线性扫描取出f最小的棋盘 */
    /* 此处可用最小堆提高效率 */
    int min_f, min_idx, i;
    States ret;

    min_f = infinity;
    min_idx = 0;
    for (i = 0; i < table->size; i++) { /* 找到f最小的棋盘 */
        if (table->t[i]->f < min_f) {
            min_f = table->t[i]->f;
            min_idx = i;
        }
    }
    ret = table->t[min_idx];
    table->t[min_idx] = table->t[table->size - 1]; /* 从table中删除该棋盘 */
    table->size--;
    return ret;
}
/* 关于OPEN和CLOSED表的定义与操作结束 */

/* 棋盘相关操作 */
long long MatrixToNumber(int m[][kSize]) {
    /* 将棋盘矩阵压缩存储为整数 */
    long long x;
    int i, j;

    x = 0;
    for (i = 0; i < kSize; i++) {
        for (j = 0; j < kSize; j++) {
            x = (x << 4) + (long long)m[i][j];
        }
    }
    return x;
}

void NumberToMatrix(long long x, int m[][kSize]) {
    /* 将整数表示的棋盘恢复为矩阵存储 */
    int i, j;

    for (i = kSize - 1; i >= 0; i--) {
        for (j = kSize - 1; j >= 0; j--) {
            m[i][j] = (int)(x % 16);
            x >>= 4;
        }
    }
}

void ReadConfig(States state) {
    /* 读入棋盘状态并存为一个整数 */
    int m[kSize][kSize], i, j;

    for (i = 0; i < kSize; i++) {
        for (j = 0; j < kSize; j++) {
            scanf("%d", &m[i][j]);
        }
    }
    state->s = MatrixToNumber(m);
}

States NextConfig(States state, int direction) {
    /* 根据移动方向direction生成下一个棋盘布局 */
    /* 若该方向的移动不可能，则返回 NULL */
    States next;
    int i, j, i0, j0;
    long long x;
    int m[kSize][kSize] = {0};

    /* 将当前棋盘转换成3x3的矩阵存储 */
    x = state->s;
    NumberToMatrix(x, m);
    for (i = 0; i < kSize; i++) { /* 找到0所在的位置 */
        for (j = 0; j < kSize; j++) {
            if (m[i][j] == 0) {
                i0 = i;
                j0 = j;
                break;
            }
        }
        if (j < kSize) {
            break;
        }
    }
    switch (direction) { /* 根据direction执行移动操作 */
    case 0: /* 从上向下移动 */
        if (i0 == 0) { /* 上面没有空格 */
            return NULL;
        } else {
            m[i0][j0] = m[i0 - 1][j0];
            m[i0 - 1][j0] = 0;
        }
        break;
    case 1: /* 从下向上移动 */
        if (i0 == 2) { /* 下面没有空格 */
            return NULL;
        } else {
            m[i0][j0] = m[i0 + 1][j0];
            m[i0 + 1][j0] = 0;
        }
        break;
    case 2: /* 从左向右移动 */
        if (j0 == 0) { /* 左边没有空格 */
            return NULL;
        } else {
            m[i0][j0] = m[i0][j0 - 1];
            m[i0][j0 - 1] = 0;
        }
        break;
    case 3: /* 从右向左移动 */
        if (j0 == 2) { /* 右边没有空格 */
            return NULL;
        } else {
            m[i0][j0] = m[i0][j0 + 1];
            m[i0][j0 + 1] = 0;
        }
        break;
    default:
        break;
    }
    /* 至此当前移动已经在矩阵m中成功执行 */
    next = (States)malloc(sizeof(struct StateNode)); /* 创建新的棋盘 */
    /* 将m转存为整数 */
    next->s = MatrixToNumber(m);
    return next;
}
/* 棋盘相关操作结束 */

int h(States X, States T) {
    /* 求棋盘X与棋盘T上不同的格子数量 */
    int count, i;
    long long x, t;

    x = X->s;
    t = T->s;
    count = 0;
    for (i = 0; i < kSize; i++) {
        if (x % 16 != t % 16) { /* 比较当前格子 */
            count++;
        }
        x >>= 4;
        t >>= 4;
    }
    return count;
}

void Update(States Y, int new_cost, States X, States T) {
    Y->g = new_cost; /* 更新g(Y)*/
    Y->f = Y->g + h(Y, T); /* 更新f(Y)*/
    Y->parent = X; /* 将Y的父结点设置为X，记录解的路径 */
}

/* 算法16-4：A算法 A ( h, init_state, goal_state) */
States A(int (*h)(States X, States T), States init_state, States goal_state) {
    Tables OPEN, CLOSED;
    States X, Y;
    int direction, new_cost;

    OPEN = (Tables)malloc(sizeof(struct TableNode));
    OPEN->size = 0;
    CLOSED = (Tables)malloc(sizeof(struct TableNode));
    CLOSED->size = 0;
    Insert(OPEN, init_state); /* 将初始状态加入OPEN表 */
    init_state->g = 0;
    init_state->f = init_state->g + h(init_state, goal_state);
    while (IsEmpty(OPEN) == false) {
        X = ExtractMin(OPEN); /* 从OPEN表中选择f值最小的结点X */
        Insert(CLOSED, X); /* 将X放入CLOSED表中 */
        if (X->s == goal_state->s) {
            return X; /* 成功找到解 */
        }
        for (direction = 0; direction < 4; direction++) {
            Y = NextConfig(X, direction); /* 对每个由X扩展出的状态Y */
            if (Y != NULL) {
                new_cost = X->g + 1;
                if (IsIn(OPEN, Y) == false && IsIn(CLOSED, Y) == false) {
                    Insert(OPEN, Y); /* 将Y放入OPEN表中 */
                    Update(Y, new_cost, X, goal_state); /* 更新Y的状态 */
                } else if (IsIn(OPEN, Y) == true && new_cost < Y->g) {
                    Update(Y, new_cost, X, goal_state); /* 更新Y的状态 */
                } else if (IsIn(CLOSED, Y) == true && new_cost < Y->g) {
                    Remove(CLOSED, Y); /* 将Y从CLOSED表移入OPEN表 */
                    Insert(OPEN, Y);
                    Update(Y, new_cost, X, goal_state); /* 更新Y的状态 */
                }
            }
        }
    }
    return NULL; /* 未找到解 */
}
/* 算法16-4 结束 */

void PrintSolution(States state) {
    /* 打印从初始状态到state的每一步棋盘 */
    int i, j, m[kSize][kSize];

    if (state->parent != NULL) {
        PrintSolution(state->parent); /* 递归打印前面的棋盘 */
    }
    /* 打印当前棋盘 */
    NumberToMatrix(state->s,
                   m); /* 将整数表示的棋盘恢复为矩阵存储 */
    printf("Step %d:\n", state->g);
    for (i = 0; i < kSize; i++) { /* 打印矩阵 */
        printf("%d", m[i][0]);
        for (j = 1; j < kSize; j++) {
            printf(" %d", m[i][j]);
        }
        printf("\n");
    }
}

int main(void) {
    States init_state, goal_state;

    init_state = (States)malloc(sizeof(struct StateNode));
    ReadConfig(init_state);
    init_state->parent = NULL;
    goal_state = (States)malloc(sizeof(struct StateNode));
    ReadConfig(goal_state);
    goal_state = A(h, init_state, goal_state);
    if (goal_state != NULL) {
        PrintSolution(goal_state);
    } else {
        printf("No Solution.\n");
    }

    return 0;
}